GATE CSE 2004


Q21.

A 4-bit carry look ahead Combinational Circuit, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the Combinational Circuit? Assume that the carry network has been implemented using two-level AND-OR logic.
GateOverflow

Q22.

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different value
GateOverflow

Q23.

A hard disk with a transfer rate of 10 Mbytes/second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation?
GateOverflow

Q24.

Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
GateOverflow

Q25.

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?
GateOverflow

Q26.

The inclusion of which of the following sets into S = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?
GateOverflow

Q27.

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n=d_{1}d_{2}...d_{m}. int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } The loop invariant condition at the end of the i^{th} iteration is:
GateOverflow

Q28.

Consider the following C program main() { int x, y, m, n; scanf ("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m = x; n = y; while (m! = n) { if (m > n) m = m - n; else n = n - m; } print f ("% d", n); } The program computes
GateOverflow

Q29.

What does the following algorithm approximate? (Assume m \gt 1, e \gt 0). x = m; y = 1; while (x - y > e) { x = (x + y)/2; y = m/x; } print(x);
GateOverflow

Q30.

The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies: name, courseNo, \rightarrow grade rollNo, courseNo \rightarrow grade name \rightarrow rollNo rollNo \rightarrow name The highest normal form of this relation scheme is
GateOverflow